62. Unique Paths
Medium

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

 

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

 

Constraints:

  • 1 <= m, n <= 100
  • It's guaranteed that the answer will be less than or equal to 2 * 109.
Accepted
662,169
Submissions
1,163,693
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.74 (38 votes)

Premium

Solution


Overview

Since robot can move either down or right, there is only one path to reach the cells in the first row: right->right->...->right.

traversal

The same is valid for the first column, though the path here is down->down-> ...->down.

traversal

What about the "inner" cells (m, n)? To such cell one could move either from the upper cell (m, n - 1), or from the cell on the right (m - 1, n). That means that the total number of paths to move into (m, n) cell is uniquePaths(m - 1, n) + uniquePaths(m, n - 1).

traversal

Now, one could transform these ideas into 3-liner recursive solution:

This solution is not fast enough to pass all the testcases, though it could be used as a starting point for the DP solution.


Approach 1: Dynamic Programming

One could rewrite recursive approach into dynamic programming one.

Algorithm

  • Initiate 2D array d[m][n] = number of paths. To start, put number of paths equal to 1 for the first row and the first column. For the simplicity, one could initiate the whole 2D array by ones.

  • Iterate over all "inner" cells: d[col][row] = d[col - 1][row] + d[col][row - 1].

  • Return d[m - 1][n - 1].

Implementation

Current
1 / 13

Complexity Analysis

  • Time complexity: O(N×M)\mathcal{O}(N \times M).

  • Space complexity: O(N×M)\mathcal{O}(N \times M).


Approach 2: Math (Python3 only)

Could one do better than O(N×M)\mathcal{O}(N \times M)? The answer is yes.

The problem is a classical combinatorial problem: there are h+vh + v moves to do from start to finish, h=m1h = m - 1 horizontal moves, and v=n1v = n - 1 vertical ones. One could choose when to move to the right, i.e. to define hh horizontal moves, and that will fix vertical ones. Or, one could choose when to move down, i.e. to define vv vertical moves, and that will fix horizontal ones.

traversal

In other words, we're asked to compute in how many ways one could choose pp elements from p+kp + k elements. In mathematics, that's called binomial coefficients

Ch+vh=Ch+vv=(h+v)!h!v! C_{h + v}^{h} = C_{h + v}^{v} = \frac{(h + v)!}{h! v!}

The number of horizontal moves to do is h=m1h = m - 1, the number of vertical moves is v=n1v = n - 1. That results in a simple formula

Ch+vh=(m+n2)!(m1)!(n1)! C_{h + v}^{h} = \frac{(m + n - 2)!}{(m - 1)! (n - 1)!}

The job is done. Now time complexity will depend on the algorithm to compute factorial function (m+n2)!(m + n - 2)!. In short, standard computation for k!k! using the definition requires O(k2logk)\mathcal{O}(k^2 \log k) time, and that will be not as good as DP algorithm.

The best known algorithm to compute factorial function is done by Peter Borwein. The idea is to express the factorial as a product of prime powers, so that k!k! can be computed in O(k(logkloglogk)2)\mathcal{O}(k (\log k \log \log k)^2) time. That's better than O(k2)\mathcal{O}(k^2) and hence beats DP algorithm.

The authors prefer not to discuss here various factorial function implementations, and hence provide Python3 solution only, with built-in divide and conquer factorial algorithm. If you're interested in factorial algorithms, please check out good review on this page.

Implementation

Complexity Analysis

  • Time complexity: O((M+N)(log(M+N)loglog(M+N))2)\mathcal{O}((M + N) (\log (M + N) \log \log (M + N))^2).

  • Space complexity: O(1)\mathcal{O}(1).

Report Article Issue

Comments: 37
ntkw's avatar
Read More

3rd solution time complexity is something evil

259
Show 2 replies
Reply
Share
Report
campiador's avatar
Read More

In the second solution (DP) we only need one row to keep, and we can keep reading from and updating it. That would result in O(n) space instead of O(m*n);

62
Show 3 replies
Reply
Share
Report
Xyzzy123's avatar
Read More

In Python 3.8, there's a new function that calculates n-choose-k directly:

def uniquePaths(self, m: int, n: int) -> int:
    return math.comb(m + n - 2, n - 1)

26
Show 2 replies
Reply
Share
Report
theseungjin's avatar
Read More

A bit confused by the code for DP implementation. When you create DP table, you use 'n' as the columns. But in the for loop, to iterate over 'col' you use range(1, m). I understand the output is not affected, but the code causes confusion in understanding

16
Show 2 replies
Reply
Share
Report
warland's avatar
Read More

Here is an easy Java Version.

// Runtime: O(M*N) Memory: O(N)
public int uniquePaths(int m, int n) {
	int[] dp = new int[n];
	Arrays.fill(dp, 1);
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			dp[j] = dp[j] + dp[j - 1];
		}
	}
	return dp[n - 1];
}

21
Reply
Share
Report
zlobspb's avatar
Read More

DP solution doesn't have to hold the whole 2D array.
Only one line needed, so the memory usage becomes O(min(M, N))

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m > n:
            m, n = n, m
        r = [1] * m
        for _ in range(1, n):
            for i in range(1, m):
                r[i] += r[i - 1]
        return r[-1]

9
Show 3 replies
Reply
Share
Report
ggaswint's avatar
Read More

Can we not do this in linear time O(m+n) as shown below? I am confused by the statement that, "The best known algorithm to compute factorial function is done by Peter Borwein [and is some crazy complexity]". Honestly I did not read the paper, I was hoping someone could have a layman explanation such as, "because the number of digits grows quickly, multiplication can no longer be thought of as a constant operation".

class Solution {
    public int uniquePaths(int m, int n) {
        double num = 1;
        double denom = 1;
        for(int i = 2; i < Math.min(m,n); i++){
            denom*=i;
        }
        for(int i = Math.max(m,n); i <= m+n-2; i++){
            num*=i;
        }
        return (int) (num/(denom));  
    }
}

3
Show 1 reply
Reply
Share
Report
ztztzt8888's avatar
Read More

The recursion method is quite intuitive, it only needs memorization to pass the tests.

    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        return uniquePaths(memo, m - 1, n - 1);
    }

    private int uniquePaths(int[][] memo, int r, int c) {
        if (r == 0 || c == 0) return memo[r][c] = 1;
        if (memo[r][c] != 0) return memo[r][c];
        return memo[r][c] = uniquePaths(memo, r - 1, c) + uniquePaths(memo, r, c - 1);
    }

The simplest math solution in Java needs BigInteger.

import java.math.BigInteger;

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        return factorial(m + n - 2).divide(factorial(m - 1)).divide(factorial(n - 1)).intValue();
    }

    public BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
            result = result.multiply(BigInteger.valueOf(i));
        return result;
    }
}

4
Show 1 reply
Reply
Share
Report
rite2riddhi's avatar
Read More

are we really expected to come up with the apporach 3 solution in a real interview?

4
Show 3 replies
Reply
Share
Report
vladlazar94's avatar
Read More

I love the illustrations ;) Very subtle Android commercial :P

2
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
03/27/2021 08:02Accepted0 ms5.9 MBcpp
06/30/2020 07:41Accepted0 ms6.1 MBcpp
05/18/2020 16:22Accepted0 ms6 MBcpp
05/18/2020 16:21Wrong AnswerN/AN/Acpp
05/18/2020 16:20Runtime ErrorN/AN/Acpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.